package sort.advance;

import java.util.Arrays;

/**
 * 归并排序
 * @author caasi
 * @since 2022-01-05 09:06:52
 */
public class MergeSort {

    public static void main(String[] args) {
        int n = 100000000;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int r = (int) (Math.random() * 1000);
            arr[i] = r;
        }
        //int arr[] = new int[]{56,74,34,24,89,112,34,21,12,9};
        //System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        MergeSort.sort(arr);
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end - start) + "ms");
        //System.out.println(Arrays.toString(arr));
    }

    private static int[] assist;

    public static void sort(int[] arr) {
        assist = new int[arr.length];
        int low = 0;
        int high = arr.length - 1;
        sort(arr, low, high);
    }

    private static void sort(int[] arr, int low, int high) {
        //递归出口
        if (high <= low) {
            return;
        }
        //分组 每次劈开一半
        int middle = low + (high - low) / 2;
        //进行递归
        sort(arr, low, middle);
        sort(arr, middle + 1, high);
        //归并
        merge(arr, low, middle, high);
    }

    private static void merge(int arr[], int low, int middle, int high) {
        int p1 = low;
        int p2 = middle + 1;
        int p3 = low;
        //同时移动p1与p2，总有一个会先到达末尾而另一个没到达
        while (p1 <= middle && p2 <= high) {
            if (arr[p1] < arr[p2]) {
                assist[p3++] = arr[p1++];
            } else {
                assist[p3++] = arr[p2++];
            }
        }
        //检查p1，p2谁没有到达 并使其到达末尾
        while (p1 <= middle) {
            assist[p3++] = arr[p1++];
        }
        while (p2 <= high) {
            assist[p3++] = arr[p2++];
        }
        //将辅助数组对应的元素复制到原数组的位置
        for (int i = low; i <= high; i++) {
            arr[i] = assist[i];
        }
    }
}
